  


<!DOCTYPE html>
<html>
  <head prefix="og: http://ogp.me/ns# fb: http://ogp.me/ns/fb# githubog: http://ogp.me/ns/fb/githubog#">
    <meta charset='utf-8'>
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
        <title>c-skiplist/Readme.md at master · kchmck/c-skiplist · GitHub</title>
    <link rel="search" type="application/opensearchdescription+xml" href="/opensearch.xml" title="GitHub" />
    <link rel="fluid-icon" href="https://github.com/fluidicon.png" title="GitHub" />
    <link rel="shortcut icon" href="/favicon.ico" type="image/x-icon" />

    
    

    <meta content="authenticity_token" name="csrf-param" />
<meta content="uBrbSWPPpvyK5DfZAr6qphrjZy9/hAspxVpnr2zVCa8=" name="csrf-token" />

    <link href="https://a248.e.akamai.net/assets.github.com/stylesheets/bundles/github-9bfe5392603ed50cc8ec639eef8547c72110f8b5.css" media="screen" rel="stylesheet" type="text/css" />
    <link href="https://a248.e.akamai.net/assets.github.com/stylesheets/bundles/github2-46369bcd6479421862314f2e59570847210cac02.css" media="screen" rel="stylesheet" type="text/css" />
    
    


    <script src="https://a248.e.akamai.net/assets.github.com/javascripts/bundles/frameworks-a450c7f907bdc1ee6b362ab1ecca811c761fd259.js" type="text/javascript"></script>
    
    <script defer="defer" src="https://a248.e.akamai.net/assets.github.com/javascripts/bundles/github-f1fad2ed9194836b20bb344d6db2853746913216.js" type="text/javascript"></script>
    
    

      <link rel='permalink' href='/kchmck/c-skiplist/blob/34875a853e114423fe29fd1a050022cfe896ec57/Readme.md'>
    <meta property="og:title" content="c-skiplist"/>
    <meta property="og:type" content="githubog:gitrepository"/>
    <meta property="og:url" content="https://github.com/kchmck/c-skiplist"/>
    <meta property="og:image" content="https://a248.e.akamai.net/assets.github.com/images/gravatars/gravatar-140.png?1329920549"/>
    <meta property="og:site_name" content="GitHub"/>
    <meta property="og:description" content="A skip list structure in C. Contribute to c-skiplist development by creating an account on GitHub."/>

    <meta name="description" content="A skip list structure in C. Contribute to c-skiplist development by creating an account on GitHub." />

  <link href="https://github.com/kchmck/c-skiplist/commits/master.atom" rel="alternate" title="Recent Commits to c-skiplist:master" type="application/atom+xml" />

  </head>


  <body class="logged_out page-blob windows vis-public env-production " data-blob-contribs-enabled="yes">
    <div id="wrapper">

    
    
    

      <div id="header" class="true clearfix">
        <div class="container clearfix">
          <a class="site-logo" href="https://github.com/">
            <!--[if IE]>
            <img alt="GitHub" class="github-logo" src="https://a248.e.akamai.net/assets.github.com/images/modules/header/logov7.png?1329920549" />
            <img alt="GitHub" class="github-logo-hover" src="https://a248.e.akamai.net/assets.github.com/images/modules/header/logov7-hover.png?1329920549" />
            <![endif]-->
            <img alt="GitHub" class="github-logo-4x" height="30" src="https://a248.e.akamai.net/assets.github.com/images/modules/header/logov7@4x.png?1337118065" />
            <img alt="GitHub" class="github-logo-4x-hover" height="30" src="https://a248.e.akamai.net/assets.github.com/images/modules/header/logov7@4x-hover.png?1337118065" />
          </a>

                  <!--
      make sure to use fully qualified URLs here since this nav
      is used on error pages on other domains
    -->
    <ul class="top-nav logged_out">
        <li class="pricing"><a href="https://github.com/plans">Signup and Pricing</a></li>
        <li class="explore"><a href="https://github.com/explore">Explore GitHub</a></li>
      <li class="features"><a href="https://github.com/features">Features</a></li>
        <li class="blog"><a href="https://github.com/blog">Blog</a></li>
      <li class="login"><a href="https://github.com/login?return_to=%2Fkchmck%2Fc-skiplist%2Fblob%2Fmaster%2FReadme.md">Login</a></li>
    </ul>



          
        </div>
      </div>

      

            <div class="site hfeed" itemscope itemtype="http://schema.org/WebPage">
      <div class="container hentry">
        <div class="pagehead repohead instapaper_ignore readability-menu">
        <div class="title-actions-bar">
          



              <ul class="pagehead-actions">



          <li>
            <span class="watch-button"><a href="/login?return_to=%2Fkchmck%2Fc-skiplist" class="minibutton btn-watch js-toggler-target entice tooltipped leftwards" title="You must be logged in to use this feature" rel="nofollow"><span class="icon"></span> Watch</a><a class="social-count js-social-count" href="/kchmck/c-skiplist/watchers">3</a></span>
          </li>
          <li>
            <a href="/login?return_to=%2Fkchmck%2Fc-skiplist" class="minibutton btn-fork js-toggler-target fork-button entice tooltipped leftwards"  title="You must be logged in to use this feature" rel="nofollow"><span class="icon"></span>Fork</a><a href="/kchmck/c-skiplist/network" class="social-count">1</a>
          </li>

    </ul>

          <h1 itemscope itemtype="http://data-vocabulary.org/Breadcrumb" class="entry-title public">
            <span class="repo-label"><span>public</span></span>
            <span class="mega-icon mega-icon-public-repo"></span>
            <span class="author vcard">
<a href="/kchmck" class="url fn" itemprop="url" rel="author">              <span itemprop="title">kchmck</span>
              </a></span> /
            <strong><a href="/kchmck/c-skiplist" class="js-current-repository">c-skiplist</a></strong>
          </h1>
        </div>

          

  <ul class="tabs">
    <li><a href="/kchmck/c-skiplist" class="selected" highlight="repo_sourcerepo_downloadsrepo_commitsrepo_tagsrepo_branches">Code</a></li>
    <li><a href="/kchmck/c-skiplist/network" highlight="repo_network">Network</a>
    <li><a href="/kchmck/c-skiplist/pulls" highlight="repo_pulls">Pull Requests <span class='counter'>0</span></a></li>

      <li><a href="/kchmck/c-skiplist/issues" highlight="repo_issues">Issues <span class='counter'>1</span></a></li>


    <li><a href="/kchmck/c-skiplist/graphs" highlight="repo_graphsrepo_contributors">Graphs</a></li>

  </ul>
 
<div class="frame frame-center tree-finder" style="display:none"
      data-tree-list-url="/kchmck/c-skiplist/tree-list/34875a853e114423fe29fd1a050022cfe896ec57"
      data-blob-url-prefix="/kchmck/c-skiplist/blob/34875a853e114423fe29fd1a050022cfe896ec57"
    >

  <div class="breadcrumb">
    <span class="bold"><a href="/kchmck/c-skiplist">c-skiplist</a></span> /
    <input class="tree-finder-input js-navigation-enable" type="text" name="query" autocomplete="off" spellcheck="false">
  </div>

    <div class="octotip">
      <p>
        <a href="/kchmck/c-skiplist/dismiss-tree-finder-help" class="dismiss js-dismiss-tree-list-help" title="Hide this notice forever" rel="nofollow">Dismiss</a>
        <span class="bold">Octotip:</span> You've activated the <em>file finder</em>
        by pressing <span class="kbd">t</span> Start typing to filter the
        file list. Use <span class="kbd badmono">↑</span> and
        <span class="kbd badmono">↓</span> to navigate,
        <span class="kbd">enter</span> to view files.
      </p>
    </div>

  <table class="tree-browser" cellpadding="0" cellspacing="0">
    <tr class="js-header"><th>&nbsp;</th><th>name</th></tr>
    <tr class="js-no-results no-results" style="display: none">
      <th colspan="2">No matching files</th>
    </tr>
    <tbody class="js-results-list js-navigation-container">
    </tbody>
  </table>
</div>

<div id="jump-to-line" style="display:none">
  <h2>Jump to Line</h2>
  <form accept-charset="UTF-8">
    <input class="textfield" type="text">
    <div class="full-button">
      <button type="submit" class="classy">
        <span>Go</span>
      </button>
    </div>
  </form>
</div>


<div class="subnav-bar">

  <ul class="actions subnav">
    <li><a href="/kchmck/c-skiplist/tags" class="blank" highlight="repo_tags">Tags <span class="counter">0</span></a></li>
    <li><a href="/kchmck/c-skiplist/downloads" class="blank downloads-blank" highlight="repo_downloads">Downloads <span class="counter">0</span></a></li>
    
  </ul>

  <ul class="scope">
    <li class="switcher">

      <div class="context-menu-container js-menu-container js-context-menu">
        <a href="#"
           class="minibutton bigger switcher js-menu-target js-commitish-button btn-branch repo-tree"
           data-hotkey="w"
           data-master-branch="master"
           data-ref="master">
           <span><span class="icon"></span><i>branch:</i> master</span>
        </a>

        <div class="context-pane commitish-context js-menu-content">
          <a href="javascript:;" class="close js-menu-close"><span class="mini-icon mini-icon-remove-close"></span></a>
          <div class="context-title">Switch Branches/Tags</div>
          <div class="context-body pane-selector commitish-selector js-navigation-container">
            <div class="filterbar">
              <input type="text" id="context-commitish-filter-field" class="js-navigation-enable" placeholder="Filter branches/tags" data-filterable />

              <ul class="tabs">
                <li><a href="#" data-filter="branches" class="selected">Branches</a></li>
                <li><a href="#" data-filter="tags">Tags</a></li>
              </ul>
            </div>

            <div class="js-filter-tab js-filter-branches" data-filterable-for="context-commitish-filter-field">
              <div class="no-results js-not-filterable">Nothing to show</div>
                <div class="commitish-item branch-commitish selector-item js-navigation-item js-navigation-target">
                  <h4>
                      <a href="/kchmck/c-skiplist/blob/master/Readme.md" class="js-navigation-open" data-name="master" rel="nofollow">master</a>
                  </h4>
                </div>
            </div>

            <div class="js-filter-tab js-filter-tags" style="display:none" data-filterable-for="context-commitish-filter-field">
              <div class="no-results js-not-filterable">Nothing to show</div>
            </div>
          </div>
        </div><!-- /.commitish-context-context -->
      </div>

    </li>
  </ul>

  <ul class="subnav with-scope">

    <li><a href="/kchmck/c-skiplist" class="selected" highlight="repo_source">Files</a></li>
    <li><a href="/kchmck/c-skiplist/commits/master" highlight="repo_commits">Commits</a></li>
    <li><a href="/kchmck/c-skiplist/branches" class="" highlight="repo_branches" rel="nofollow">Branches <span class="counter">1</span></a></li>
  </ul>

</div>

  
  
  


          

        </div><!-- /.repohead -->

        





<!-- block_view_fragment_key: views10/v8/blob:v21:68bafa51c72acba64650d802d40079ca -->
  <div id="slider">

    <div class="breadcrumb" data-path="Readme.md/">
      <b itemscope="" itemtype="http://data-vocabulary.org/Breadcrumb"><a href="/kchmck/c-skiplist/tree/34875a853e114423fe29fd1a050022cfe896ec57" class="js-rewrite-sha" itemprop="url"><span itemprop="title">c-skiplist</span></a></b> / <strong class="final-path">Readme.md</strong> <span class="js-clippy mini-icon mini-icon-clippy " data-clipboard-text="Readme.md" data-copied-hint="copied!" data-copy-hint="copy to clipboard"></span>
    </div>


      <div class="commit file-history-tease" data-path="Readme.md/">
        <img class="main-avatar" height="24" src="https://secure.gravatar.com/avatar/9b7731e3e20c5aa66d0cebfefc12b57e?s=140&amp;d=https://a248.e.akamai.net/assets.github.com%2Fimages%2Fgravatars%2Fgravatar-140.png" width="24" />
        <span class="author"><a href="/kchmck">kchmck</a></span>
        <time class="js-relative-date" datetime="2010-12-26T07:47:39-08:00" title="2010-12-26 07:47:39">December 26, 2010</time>
        <div class="commit-title">
            <a href="/kchmck/c-skiplist/commit/0a063619114c7b7ba066f23b96d0e6c0fed6f523" class="message">Update prototypes</a>
        </div>

        <div class="participation">
          <p class="quickstat"><a href="#blob_contributors_box" rel="facebox"><strong>1</strong> contributor</a></p>
          
        </div>
        <div id="blob_contributors_box" style="display:none">
          <h2>Users on GitHub who have contributed to this file</h2>
          <ul class="facebox-user-list">
            <li>
              <img height="24" src="https://secure.gravatar.com/avatar/9b7731e3e20c5aa66d0cebfefc12b57e?s=140&amp;d=https://a248.e.akamai.net/assets.github.com%2Fimages%2Fgravatars%2Fgravatar-140.png" width="24" />
              <a href="/kchmck">kchmck</a>
            </li>
          </ul>
        </div>
      </div>

    <div class="frames">
      <div class="frame frame-center" data-path="Readme.md/" data-permalink-url="/kchmck/c-skiplist/blob/34875a853e114423fe29fd1a050022cfe896ec57/Readme.md" data-title="c-skiplist/Readme.md at master · kchmck/c-skiplist · GitHub" data-type="blob">

        <div id="files" class="bubble">
          <div class="file">
            <div class="meta">
              <div class="info">
                <span class="icon"><b class="mini-icon mini-icon-text-file"></b></span>
                <span class="mode" title="File Mode">100644</span>
                  <span>389 lines (269 sloc)</span>
                <span>11.178 kb</span>
              </div>
              <ul class="button-group actions">
                  <li>
                    <a class="grouped-button file-edit-link minibutton bigger lighter js-rewrite-sha" href="/kchmck/c-skiplist/edit/34875a853e114423fe29fd1a050022cfe896ec57/Readme.md" data-method="post" rel="nofollow" data-hotkey="e">Edit this file</a>
                  </li>

                <li>
                  <a href="/kchmck/c-skiplist/raw/master/Readme.md" class="minibutton btn-raw grouped-button bigger lighter" id="raw-url"><span class="icon"></span>Raw</a>
                </li>
                  <li>
                    <a href="/kchmck/c-skiplist/blame/master/Readme.md" class="minibutton btn-blame grouped-button bigger lighter"><span class="icon"></span>Blame</a>
                  </li>
                <li>
                  <a href="/kchmck/c-skiplist/commits/master/Readme.md" class="minibutton btn-history grouped-button bigger lighter" rel="nofollow"><span class="icon"></span>History</a>
                </li>
              </ul>
            </div>
            
  <div id="readme" class="blob instapaper_body">
    <article class="markdown-body entry-content" itemprop="mainContentOfPage"><h1>
<a name="c-skiplist-api-reference" class="anchor" href="#c-skiplist-api-reference"><span class="mini-icon mini-icon-link"></span></a>C-Skiplist API Reference</h1>

<h2>
<a name="the-setup" class="anchor" href="#the-setup"><span class="mini-icon mini-icon-link"></span></a>The Setup</h2>

<p>The rest of the reference will refer to the following structure in examples:</p>

<pre><code>typedef struct {
  char *key;
  int id;
  int value;
} test_t;
</code></pre>

<h2>
<a name="core-types" class="anchor" href="#core-types"><span class="mini-icon mini-icon-link"></span></a>Core Types</h2>

<ul>
<li><strong>skiplist_t</strong></li>
</ul><p>The core skiplist structure.</p>

<pre><code>skiplist_t list;
</code></pre>

<ul>
<li>
<strong>skiplist_cmp_t</strong> = <em>intmax_t</em>
</li>
</ul><p>A comparison result – a <em>negative number</em> means <em>less than</em>, a <em>positive number</em>
means <em>greater than</em>, and <em>zero</em> means <em>equality</em>. The <strong>SKIPLIST<em>CMP</em>\</strong>*
constants can be used for clarity or convenience.</p>

<ul>
<li>
<strong>skiplist_length_t</strong> = <em>uintmax_t</em>
</li>
</ul><p>A skiplist's length – the number of values it holds.</p>

<h2>
<a name="callback-functions" class="anchor" href="#callback-functions"><span class="mini-icon mini-icon-link"></span></a>Callback Functions</h2>

<ul>
<li><strong>skiplist_cmp_fn</strong></li>
</ul><p>Compare <em>list_value</em> and <em>user_value</em> to determine sorting. A return value less
than or equal to <strong>SKIPLIST_CMP_LT</strong> – a negative number – means <em>list_value</em>
should be before <em>user_value</em>. A return value equal to <strong>SKIPLIST_CMP_EQ</strong> –
zero – means <em>list_value</em> is <em>user_value</em>. A return value greater than or equal
to <strong>SKIPLIST_CMP_GT</strong> – a positive number – means <em>list_value</em> should be after
<em>user_value</em>.</p>

<pre><code>typedef skiplist_cmp_t (*skiplist_cmp_fn)(const void *list_value,
                                          const void *user_value);
</code></pre>

<p>Given a compare function like:</p>

<pre><code>skiplist_cmp_t cmp(const void *list_value, const void *user_value) {
  const test_t *l = list_value;
  const test_t *u = user_value;

  return strcmp(l-&gt;key, u-&gt;key);
}
</code></pre>

<p>The <strong>skiplist_set_cmp_fn</strong> function could be used to associate it with a
skiplist:</p>

<pre><code>skiplist_set_cmp_fn(&amp;list, cmp);
</code></pre>

<ul>
<li><strong>skiplist_search_fn</strong></li>
</ul><p>Used by <strong>skiplist_search</strong> to compare a skiplist value to a search value.</p>

<pre><code>typedef skiplist_cmp_t (*skiplist_search_fn)(const void *value,
                                             const void *search);
</code></pre>

<p>The following search function could be used to search for a <code>test_t</code> by its key
– a string:</p>

<pre><code>skiplist_cmp_t search(const void *value, const void *search) {
  const test_t *test = value;
  const char *search_key = search;

  return strcmp(test-&gt;key, search_key);
}
</code></pre>

<p>It could be associated with a skiplist using <strong>skiplist_set_search_fn</strong>:</p>

<pre><code>skiplist_set_search_fn(&amp;list, search);
</code></pre>

<p>The <strong>skiplist_search</strong> function could then be used like:</p>

<pre><code>test_t *found_test = skiplist_search(&amp;list, "abcdef");
</code></pre>

<ul>
<li><strong>skiplist_destroy_fn</strong></li>
</ul><p>Optionally used by <strong>skiplist_delete</strong> and <strong>skiplist_destroy</strong> to destroy the
value of a node.</p>

<pre><code>typedef void (*skiplist_destroy_fn)(void *value);
</code></pre>

<p>If each value is simple and allocated on the heap, then a function like this
would work in most cases:</p>

<pre><code>void destroy(void *value) {
  free(value);
}
</code></pre>

<ul>
<li><strong>skiplist_inspect_fn</strong></li>
</ul><p>Optionally used by <strong>skiplist_inspect</strong> to pretty-print the value of a node.</p>

<pre><code>typedef bool (*skiplist_inspect_fn)(const void *value, char buffer[],
                                    const size_t buffer_size);
</code></pre>

<p>The <code>snprintf</code> function is fine for this task:</p>

<pre><code>bool inspect(const void *value, char buffer[],
             const size_t buffer_size)
{
  const test_t *test = value;

  return snprintf(buffer, buffer_size, "%s: {id: %d, value: %d}", test-&gt;key,
                                                                  test-&gt;id,
                                                                  test-&gt;value) &gt; 0;
}
</code></pre>

<p>The <strong>skiplist_set_inspect_fn</strong> function is used to associate an inspect
function with a skiplist:</p>

<pre><code>skiplist_set_inspect_fn(&amp;list, inspect);
</code></pre>

<h2>
<a name="constants" class="anchor" href="#constants"><span class="mini-icon mini-icon-link"></span></a>Constants</h2>

<ul>
<li>
<strong>SKIPLIST_CMP_LT</strong> = <em>-1</em>
</li>
<li>
<strong>SKIPLIST_CMP_EQ</strong> = <em>0</em>
</li>
<li>
<strong>SKIPLIST_CMP_GT</strong> = <em>1</em>
</li>
</ul><p>The <strong>SKIPLIST<em>CMP</em>\</strong>* constants can be used to clarify a comparison result:</p>

<pre><code>skiplist_cmp_t cmp(const void *list_value, const void *user_value) {
  const test_t *l = list_value;
  const test_t *u = user_value;

  if (l-&gt;id &lt; u-&gt;id)
    return SKIPLIST_CMP_LT;

  if (l-&gt;id &gt; u-&gt;id)
    return SKIPLIST_CMP_GT;

  return SKIPLIST_CMP_EQ;
}
</code></pre>

<h2>
<a name="initialization-and-destruction-functions" class="anchor" href="#initialization-and-destruction-functions"><span class="mini-icon mini-icon-link"></span></a>Initialization and Destruction Functions</h2>

<ul>
<li>void <strong>skiplist_global_init</strong>(<strong><em>void</em></strong>)</li>
</ul><p>Initialize the random number environment used for generating skiplist levels:</p>

<pre><code>void skiplist_global_init(void) {
  srand(time(NULL));
}
</code></pre>

<p>If your application already does something similar, then this function can be
ignored. Otherwise, <strong>this function is mandatory</strong>.</p>

<ul>
<li>bool <strong>skiplist_init</strong>(<strong><em>skiplist_t</em></strong> *<em>list</em>)</li>
</ul><p>Initialize <em>list</em>. Return <code>true</code> on success and <code>false</code> on failure. <strong>This
function is mandatory</strong> and should be the first function called on <em>list</em>.</p>

<ul>
<li>void <strong>skiplist_destroy</strong>(<strong><em>skiplist_t</em></strong> *<em>list</em>)</li>
</ul><p>Destroy <em>list</em> and free any used memory. If <em>list</em> has a destroy function, it
will be used on each value. <strong>This function is mandatory</strong> if <em>list</em> has been
initialized.</p>

<h2>
<a name="callback-setter-functions" class="anchor" href="#callback-setter-functions"><span class="mini-icon mini-icon-link"></span></a>Callback-Setter Functions</h2>

<ul>
<li>void <strong>skiplist_set_cmp_fn</strong>(<strong><em>skiplist_t</em></strong> *<em>list</em>, <strong><em>skiplist_cmp_fn</em></strong> <em>fn</em>)</li>
</ul><p>Set <em>list</em>'s compare function to <em>fn</em>. <strong>This function is mandatory</strong>.</p>

<ul>
<li>void <strong>skiplist_set_search_fn</strong>(<strong><em>skiplist_t</em></strong> *<em>list</em>, <strong><em>skiplist_search_fn</em></strong> <em>fn</em>)</li>
</ul><p>Set <em>list</em>'s search function to <em>fn</em>. <strong>This function is mandatory</strong> to use
<strong>skiplist_search</strong>.</p>

<ul>
<li>void <strong>skiplist_set_destroy_fn</strong>(<strong><em>skiplist_t</em></strong> *<em>list</em>, <strong><em>skiplist_destroy_fn</em></strong> <em>fn</em>)</li>
</ul><p>Set <em>list</em>'s destroy function to <em>fn</em>.</p>

<ul>
<li>void <strong>skiplist_set_inspect_fn</strong>(<strong><em>skiplist_t</em></strong> *<em>list</em>, <strong><em>skiplist_inspect_fn</em></strong> <em>fn</em>)</li>
</ul><p>Set <em>list</em>'s inspect function to <em>fn</em>.</p>

<h2>
<a name="operation-functions" class="anchor" href="#operation-functions"><span class="mini-icon mini-icon-link"></span></a>Operation Functions</h2>

<ul>
<li>bool <strong>skiplist_insert</strong>(<strong><em>skiplist_t</em></strong> *<em>list</em>, <strong><em>void</em></strong> *<em>value</em>)</li>
</ul><p>Insert <em>value</em> into <em>list</em>. Return <code>true</code> if <em>value</em> was inserted or already
exists and <code>false</code> otherwise. If <em>value</em> equals an existing value, as determined
by <em>list</em>'s compare function, the existing value will be deleted and <em>value</em>
will be inserted.</p>

<ul>
<li>bool <strong>skiplist_delete</strong>(<strong><em>skiplist_t</em></strong> *<em>list</em>, const <strong><em>void</em></strong> *<em>value</em>)</li>
</ul><p>Delete <em>value</em> from <em>list</em>. Return <code>true</code> if <em>value</em> was deleted and <code>false</code>
otherwise. If <em>list</em> has a destroy function, it will be used to destroy the
deleted value.</p>

<ul>
<li>bool <strong>skiplist_contains</strong>(const <strong><em>skiplist_t</em></strong> *<em>list</em>, const <strong><em>void</em></strong> *<em>value</em>)</li>
</ul><p>Check if <em>list</em> contains <em>value</em>, as determined by <em>list</em>'s compare function.
Return <code>true</code> if so and <code>false</code> if not.</p>

<ul>
<li>void *<strong>skiplist_search</strong>(<strong><em>skiplist_t</em></strong> *<em>list</em>, const <strong><em>void</em></strong> *<em>search</em>)</li>
</ul><p>Search <em>list</em> for a value that matches <em>search</em>, as determined by <em>list</em>'s
search function. Return the matching value or <code>NULL</code> if one wasn't found.</p>

<h2>
<a name="inspection-functions" class="anchor" href="#inspection-functions"><span class="mini-icon mini-icon-link"></span></a>Inspection Functions</h2>

<ul>
<li>skiplist_length_t <strong>skiplist_length</strong>(const <strong><em>skiplist_t</em></strong> *<em>list</em>)</li>
</ul><p>Get the number of values in <em>list</em>.</p>

<ul>
<li>void <strong>skiplist_inspect</strong>(const <strong><em>skiplist_t</em></strong> *<em>list</em>, <strong><em>FILE</em></strong> *<em>stream</em>)</li>
</ul><p>Pretty-print the nodes in <em>list</em> to <em>stream</em>. Output resembles the following
when <em>list</em> has no inspect function – the default:</p>

<pre><code>Header 0xc2c010 {level: 5}
  |5| -&gt; (nil)
  |4| -&gt; 0xc2c090
  |3| -&gt; 0xc2c090
  |2| -&gt; 0xc2c090
  |1| -&gt; 0xc2c090
  |0| -&gt; 0xc2c230
Node 0xc2c230 {level: 0}
  |0| -&gt; 0xc2c090
Node 0xc2c090 {level: 4}
  |4| -&gt; (nil)
  |3| -&gt; 0xc2c1c0
  |2| -&gt; 0xc2c1c0
  |1| -&gt; 0xc2c1c0
  |0| -&gt; 0xc2c1c0
Node 0xc2c1c0 {level: 3}
  |3| -&gt; (nil)
  |2| -&gt; 0xc2c100
  |1| -&gt; 0xc2c100
  |0| -&gt; 0xc2c100
Node 0xc2c100 {level: 2}
  |2| -&gt; (nil)
  |1| -&gt; (nil)
  |0| -&gt; (nil)
</code></pre>

<p>With an inspect function like this:</p>

<pre><code>bool inspect(const void *value, char buffer[],
             const skiplist_inspect_size_t buffer_size)
{
  const test_t *test = value;

  return snprintf(buffer, buffer_size, "{%s: %d}", test-&gt;key,
                                                   test-&gt;value);
}
</code></pre>

<p>Output would resemble:</p>

<pre><code>Header 0xc2c010 {level: 5}
  |5| -&gt; (nil)
  |4| -&gt; 0xc2c090
  |3| -&gt; 0xc2c090
  |2| -&gt; 0xc2c090
  |1| -&gt; 0xc2c090
  |0| -&gt; 0xc2c230
Node 0xc2c230 {level: 0, value: {def: 2}}
  |0| -&gt; 0xc2c090
Node 0xc2c090 {level: 4, value: {ghi: 4}}
  |4| -&gt; (nil)
  |3| -&gt; 0xc2c1c0
  |2| -&gt; 0xc2c1c0
  |1| -&gt; 0xc2c1c0
  |0| -&gt; 0xc2c1c0
Node 0xc2c1c0 {level: 3, value: {jkl: 5}}
  |3| -&gt; (nil)
  |2| -&gt; 0xc2c100
  |1| -&gt; 0xc2c100
  |0| -&gt; 0xc2c100
Node 0xc2c100 {level: 2, value: {mno: 6}}
  |2| -&gt; (nil)
  |1| -&gt; (nil)
  |0| -&gt; (nil)
</code></pre>

<h2>
<a name="iteration" class="anchor" href="#iteration"><span class="mini-icon mini-icon-link"></span></a>Iteration</h2>

<p>Iteration is supported through the <strong>skiplist<em>iter</em>\</strong>* type and functions.
Values are yielded as they're sorted in the skiplist.</p>

<pre><code>skiplist_iter_t iter;
skiplist_iter_init(&amp;iter, &amp;list);

test_t *test;
while ((test = skiplist_iter_next(&amp;iter)))
  printf("Got value %d\n", test-&gt;value);
</code></pre>

<ul>
<li><strong>skiplist_iter_t</strong></li>
</ul><p>An iterator that's associated with a skiplist on initialization.</p>

<ul>
<li>void <strong>skiplist_iter_init</strong>(<strong><em>skiplist_iter_t</em></strong> *<em>iter</em>, <strong><em>skiplist_t</em></strong> *<em>list</em>)</li>
</ul><p>Initialize <em>iter</em> and associate it with <em>list</em>. <strong>This function is mandatory</strong>
and must be the first function called on <em>iter</em>.</p>

<ul>
<li>void <strong>skiplist_iter_reset</strong>(<strong><em>skiplist_iter_t</em></strong> *<em>iter</em>)</li>
</ul><p>Reset <em>iter</em> to the beginning of its associated skiplist – the first value.</p>

<ul>
<li>void *<strong>skiplist_iter_next</strong>(<strong><em>skiplist_iter_t</em></strong> *<em>iter</em>)</li>
</ul><p>Return the next value from <em>iter</em> or <code>NULL</code> if there are no more.</p>

<h2>
<a name="for-example" class="anchor" href="#for-example"><span class="mini-icon mini-icon-link"></span></a>For Example</h2>

<p>This code:</p>

<pre><code>skiplist_cmp_t cmp(const void *list_value, const void *user_value) {
  const test_t *l = list_value;
  const test_t *u = user_value;

  return strcmp(l-&gt;key, u-&gt;key);
}

skiplist_cmp_t search(const void *value, const void *search) {
  const test_t *test = value;
  const char *search_key = search;

  printf("search: compare %s and %s\n", test-&gt;key, search_key);

  return strcmp(test-&gt;key, search_key);
}

void destroy(void *value) {
  printf("destroy: test #%d\n", ((test_t *)(value))-&gt;id);
}

int main() {
  skiplist_t list;
  skiplist_init(&amp;list); // -&gt; true

  skiplist_set_cmp_fn(&amp;list, cmp);
  skiplist_set_search_fn(&amp;list, search);
  skiplist_set_destroy_fn(&amp;list, destroy);

  test_t a = {"abc", 0, 42};
  test_t b = {"def", 1, 13};
  test_t c = {"ghi", 2, 7};
  test_t d = {"abc", 3, 15};

  printf("--- insert\n");
  skiplist_insert(&amp;list, &amp;a); // -&gt; true
  skiplist_insert(&amp;list, &amp;b); // -&gt; true
  skiplist_insert(&amp;list, &amp;c); // -&gt; true
  skiplist_insert(&amp;list, &amp;d); // -&gt; true

  printf("--- contains\n");
  if (skiplist_contains(&amp;list, &amp;b))
    printf("list contains test #%d\n", b.id);

  printf("--- search\n");
  const test_t *found = skiplist_search(&amp;list, "def"); // -&gt; &amp;b
  printf("found: test #%d with value %d\n", found-&gt;id, found-&gt;value);

  printf("--- delete\n");
  skiplist_delete(&amp;list, &amp;c); // -&gt; true

  printf("--- destroy\n");
  skiplist_destroy(&amp;list);

  return 0;
}
</code></pre>

<p>Produces this output:</p>

<pre><code>--- insert
destroy: test #0
--- contains
list contains test #1
--- search
search: compare abc and def
search: compare def and def
found: test #1 with value 13
--- delete
destroy: test #2
--- destroy
destroy: test #3
destroy: test #1
</code></pre></article>
  </div>

          </div>
        </div>
      </div>
    </div>

  </div>

<div class="frame frame-loading large-loading-area" style="display:none;" data-tree-list-url="/kchmck/c-skiplist/tree-list/34875a853e114423fe29fd1a050022cfe896ec57" data-blob-url-prefix="/kchmck/c-skiplist/blob/34875a853e114423fe29fd1a050022cfe896ec57">
  <img src="https://a248.e.akamai.net/assets.github.com/images/spinners/octocat-spinner-64.gif?1329920549" height="64" width="64">
</div>

      </div>
      <div class="context-overlay"></div>
    </div>

      <div id="footer-push"></div><!-- hack for sticky footer -->
    </div><!-- end of wrapper - hack for sticky footer -->

      <!-- footer -->
      <div id="footer" >
        
  <div class="upper_footer">
     <div class="container clearfix">

       <!--[if IE]><h4 id="blacktocat_ie">GitHub Links</h4><![endif]-->
       <![if !IE]><h4 id="blacktocat">GitHub Links</h4><![endif]>

       <ul class="footer_nav">
         <h4>GitHub</h4>
         <li><a href="https://github.com/about">About</a></li>
         <li><a href="https://github.com/blog">Blog</a></li>
         <li><a href="https://github.com/features">Features</a></li>
         <li><a href="https://github.com/contact">Contact &amp; Support</a></li>
         <li><a href="https://github.com/training">Training</a></li>
         <li><a href="http://enterprise.github.com/">GitHub Enterprise</a></li>
         <li><a href="http://status.github.com/">Site Status</a></li>
       </ul>

       <ul class="footer_nav">
         <h4>Tools</h4>
         <li><a href="http://get.gaug.es/">Gauges: Analyze web traffic</a></li>
         <li><a href="http://speakerdeck.com">Speaker Deck: Presentations</a></li>
         <li><a href="https://gist.github.com">Gist: Code snippets</a></li>
         <li><a href="http://mac.github.com/">GitHub for Mac</a></li>
         <li><a href="http://windows.github.com/">GitHub for Windows</a></li>
         <li><a href="http://mobile.github.com/">Issues for iPhone</a></li>
         <li><a href="http://jobs.github.com/">Job Board</a></li>
       </ul>

       <ul class="footer_nav">
         <h4>Extras</h4>
         <li><a href="http://shop.github.com/">GitHub Shop</a></li>
         <li><a href="http://octodex.github.com/">The Octodex</a></li>
       </ul>

       <ul class="footer_nav">
         <h4>Documentation</h4>
         <li><a href="http://help.github.com/">GitHub Help</a></li>
         <li><a href="http://developer.github.com/">Developer API</a></li>
         <li><a href="http://github.github.com/github-flavored-markdown/">GitHub Flavored Markdown</a></li>
         <li><a href="http://pages.github.com/">GitHub Pages</a></li>
       </ul>

     </div><!-- /.site -->
  </div><!-- /.upper_footer -->

<div class="lower_footer">
  <div class="container clearfix">
    <!--[if IE]><div id="legal_ie"><![endif]-->
    <![if !IE]><div id="legal"><![endif]>
      <ul>
          <li><a href="https://github.com/site/terms">Terms of Service</a></li>
          <li><a href="https://github.com/site/privacy">Privacy</a></li>
          <li><a href="https://github.com/security">Security</a></li>
      </ul>

      <p>&copy; 2012 <span title="0.04260s from fe15.rs.github.com">GitHub</span> Inc. All rights reserved.</p>
    </div><!-- /#legal or /#legal_ie-->

      <div class="sponsor">
        <a href="http://www.rackspace.com" class="logo">
          <img alt="Dedicated Server" height="36" src="https://a248.e.akamai.net/assets.github.com/images/modules/footer/rackspaces_logo.png?1329920549" width="38" />
        </a>
        Powered by the <a href="http://www.rackspace.com ">Dedicated
        Servers</a> and<br/> <a href="http://www.rackspacecloud.com">Cloud
        Computing</a> of Rackspace Hosting<span>&reg;</span>
      </div>
  </div><!-- /.site -->
</div><!-- /.lower_footer -->

      </div><!-- /#footer -->

    

<div id="keyboard_shortcuts_pane" class="instapaper_ignore readability-extra" style="display:none">
  <h2>Keyboard Shortcuts <small><a href="#" class="js-see-all-keyboard-shortcuts">(see all)</a></small></h2>

  <div class="columns threecols">
    <div class="column first">
      <h3>Site wide shortcuts</h3>
      <dl class="keyboard-mappings">
        <dt>s</dt>
        <dd>Focus site search</dd>
      </dl>
      <dl class="keyboard-mappings">
        <dt>?</dt>
        <dd>Bring up this help dialog</dd>
      </dl>
    </div><!-- /.column.first -->

    <div class="column middle" style='display:none'>
      <h3>Commit list</h3>
      <dl class="keyboard-mappings">
        <dt>j</dt>
        <dd>Move selection down</dd>
      </dl>
      <dl class="keyboard-mappings">
        <dt>k</dt>
        <dd>Move selection up</dd>
      </dl>
      <dl class="keyboard-mappings">
        <dt>c <em>or</em> o <em>or</em> enter</dt>
        <dd>Open commit</dd>
      </dl>
      <dl class="keyboard-mappings">
        <dt>y</dt>
        <dd>Expand URL to its canonical form</dd>
      </dl>
    </div><!-- /.column.first -->

    <div class="column last" style='display:none'>
      <h3>Pull request list</h3>
      <dl class="keyboard-mappings">
        <dt>j</dt>
        <dd>Move selection down</dd>
      </dl>
      <dl class="keyboard-mappings">
        <dt>k</dt>
        <dd>Move selection up</dd>
      </dl>
      <dl class="keyboard-mappings">
        <dt>o <em>or</em> enter</dt>
        <dd>Open issue</dd>
      </dl>
      <dl class="keyboard-mappings">
        <dt><span class="platform-mac">⌘</span><span class="platform-other">ctrl</span> <em>+</em> enter</dt>
        <dd>Submit comment</dd>
      </dl>
    </div><!-- /.columns.last -->

  </div><!-- /.columns.equacols -->

  <div style='display:none'>
    <div class="rule"></div>

    <h3>Issues</h3>

    <div class="columns threecols">
      <div class="column first">
        <dl class="keyboard-mappings">
          <dt>j</dt>
          <dd>Move selection down</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>k</dt>
          <dd>Move selection up</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>x</dt>
          <dd>Toggle selection</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>o <em>or</em> enter</dt>
          <dd>Open issue</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt><span class="platform-mac">⌘</span><span class="platform-other">ctrl</span> <em>+</em> enter</dt>
          <dd>Submit comment</dd>
        </dl>
      </div><!-- /.column.first -->
      <div class="column last">
        <dl class="keyboard-mappings">
          <dt>c</dt>
          <dd>Create issue</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>l</dt>
          <dd>Create label</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>i</dt>
          <dd>Back to inbox</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>u</dt>
          <dd>Back to issues</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>/</dt>
          <dd>Focus issues search</dd>
        </dl>
      </div>
    </div>
  </div>

  <div style='display:none'>
    <div class="rule"></div>

    <h3>Issues Dashboard</h3>

    <div class="columns threecols">
      <div class="column first">
        <dl class="keyboard-mappings">
          <dt>j</dt>
          <dd>Move selection down</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>k</dt>
          <dd>Move selection up</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>o <em>or</em> enter</dt>
          <dd>Open issue</dd>
        </dl>
      </div><!-- /.column.first -->
    </div>
  </div>

  <div style='display:none'>
    <div class="rule"></div>

    <h3>Network Graph</h3>
    <div class="columns equacols">
      <div class="column first">
        <dl class="keyboard-mappings">
          <dt><span class="badmono">←</span> <em>or</em> h</dt>
          <dd>Scroll left</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt><span class="badmono">→</span> <em>or</em> l</dt>
          <dd>Scroll right</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt><span class="badmono">↑</span> <em>or</em> k</dt>
          <dd>Scroll up</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt><span class="badmono">↓</span> <em>or</em> j</dt>
          <dd>Scroll down</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>t</dt>
          <dd>Toggle visibility of head labels</dd>
        </dl>
      </div><!-- /.column.first -->
      <div class="column last">
        <dl class="keyboard-mappings">
          <dt>shift <span class="badmono">←</span> <em>or</em> shift h</dt>
          <dd>Scroll all the way left</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>shift <span class="badmono">→</span> <em>or</em> shift l</dt>
          <dd>Scroll all the way right</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>shift <span class="badmono">↑</span> <em>or</em> shift k</dt>
          <dd>Scroll all the way up</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>shift <span class="badmono">↓</span> <em>or</em> shift j</dt>
          <dd>Scroll all the way down</dd>
        </dl>
      </div><!-- /.column.last -->
    </div>
  </div>

  <div >
    <div class="rule"></div>
    <div class="columns threecols">
      <div class="column first" >
        <h3>Source Code Browsing</h3>
        <dl class="keyboard-mappings">
          <dt>t</dt>
          <dd>Activates the file finder</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>l</dt>
          <dd>Jump to line</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>w</dt>
          <dd>Switch branch/tag</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>y</dt>
          <dd>Expand URL to its canonical form</dd>
        </dl>
      </div>
    </div>
  </div>

  <div style='display:none'>
    <div class="rule"></div>
    <div class="columns threecols">
      <div class="column first">
        <h3>Browsing Commits</h3>
        <dl class="keyboard-mappings">
          <dt><span class="platform-mac">⌘</span><span class="platform-other">ctrl</span> <em>+</em> enter</dt>
          <dd>Submit comment</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>escape</dt>
          <dd>Close form</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>p</dt>
          <dd>Parent commit</dd>
        </dl>
        <dl class="keyboard-mappings">
          <dt>o</dt>
          <dd>Other parent commit</dd>
        </dl>
      </div>
    </div>
  </div>
</div>

    <div id="markdown-help" class="instapaper_ignore readability-extra">
  <h2>Markdown Cheat Sheet</h2>

  <div class="cheatsheet-content">

  <div class="mod">
    <div class="col">
      <h3>Format Text</h3>
      <p>Headers</p>
      <pre>
# This is an &lt;h1&gt; tag
## This is an &lt;h2&gt; tag
###### This is an &lt;h6&gt; tag</pre>
     <p>Text styles</p>
     <pre>
*This text will be italic*
_This will also be italic_
**This text will be bold**
__This will also be bold__

*You **can** combine them*
</pre>
    </div>
    <div class="col">
      <h3>Lists</h3>
      <p>Unordered</p>
      <pre>
* Item 1
* Item 2
  * Item 2a
  * Item 2b</pre>
     <p>Ordered</p>
     <pre>
1. Item 1
2. Item 2
3. Item 3
   * Item 3a
   * Item 3b</pre>
    </div>
    <div class="col">
      <h3>Miscellaneous</h3>
      <p>Images</p>
      <pre>
![GitHub Logo](/images/logo.png)
Format: ![Alt Text](url)
</pre>
     <p>Links</p>
     <pre>
http://github.com - automatic!
[GitHub](http://github.com)</pre>
<p>Blockquotes</p>
     <pre>
As Kanye West said:

> We're living the future so
> the present is our past.
</pre>
    </div>
  </div>
  <div class="rule"></div>

  <h3>Code Examples in Markdown</h3>
  <div class="col">
      <p>Syntax highlighting with <a href="http://github.github.com/github-flavored-markdown/" title="GitHub Flavored Markdown" target="_blank">GFM</a></p>
      <pre>
```javascript
function fancyAlert(arg) {
  if(arg) {
    $.facebox({div:'#foo'})
  }
}
```</pre>
    </div>
    <div class="col">
      <p>Or, indent your code 4 spaces</p>
      <pre>
Here is a Python code example
without syntax highlighting:

    def foo:
      if not bar:
        return true</pre>
    </div>
    <div class="col">
      <p>Inline code for comments</p>
      <pre>
I think you should use an
`&lt;addr&gt;` element here instead.</pre>
    </div>
  </div>

  </div>
</div>


    <div id="ajax-error-message">
      <span class="mini-icon mini-icon-exclamation"></span>
      Something went wrong with that request. Please try again.
      <a href="#" class="ajax-error-dismiss">Dismiss</a>
    </div>

    <div id="logo-popup">
      <h2>Looking for the GitHub logo?</h2>
      <ul>
        <li>
          <h4>GitHub Logo</h4>
          <a href="http://github-media-downloads.s3.amazonaws.com/GitHub_Logos.zip"><img alt="Github_logo" src="https://a248.e.akamai.net/assets.github.com/images/modules/about_page/github_logo.png?1329920549" /></a>
          <a href="http://github-media-downloads.s3.amazonaws.com/GitHub_Logos.zip" class="minibutton btn-download download"><span class="icon"></span>Download</a>
        </li>
        <li>
          <h4>The Octocat</h4>
          <a href="http://github-media-downloads.s3.amazonaws.com/Octocats.zip"><img alt="Octocat" src="https://a248.e.akamai.net/assets.github.com/images/modules/about_page/octocat.png?1329920549" /></a>
          <a href="http://github-media-downloads.s3.amazonaws.com/Octocats.zip" class="minibutton btn-download download"><span class="icon"></span>Download</a>
        </li>
      </ul>
    </div>

    
    
    
    <span id='server_response_time' data-time='0.04479' data-host='fe15'></span>
  </body>
</html>

